package jjn.round2;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Jiang Jining
 * @since 2023-05-13 10:16
 */
public class Offer41_MedianFinder {
    static class MedianFinder {
        
        private final Queue<Integer> maxQueue;
        private final Queue<Integer> minQueue;
        
        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            minQueue = new PriorityQueue<>((a, b) -> (b - a));
            maxQueue = new PriorityQueue<>((a, b) -> (a - b));
        }
        
        public void addNum(int num) {
            if (minQueue.isEmpty() || minQueue.peek() >= num) {
                minQueue.offer(num);
                if (minQueue.size() > maxQueue.size() + 1) {
                    maxQueue.offer(minQueue.poll());
                }
            } else {
                maxQueue.offer(num);
                if (maxQueue.size() > minQueue.size()) {
                    minQueue.offer(maxQueue.poll());
                }
            }
        }
        
        public double findMedian() {
            if (minQueue.isEmpty()) {
                return 0;
            }
            int sizeMin = minQueue.size();
            int sizeMax = maxQueue.size();
            if (sizeMax != sizeMin) {
                return minQueue.peek();
            }
            return (minQueue.peek() + maxQueue.peek()) / 2.0;
        }
    }
}
